package com.leetcodehot.problems;

import java.util.Arrays;

public class problems198 {
    /**
     * 解法一：记忆化搜索子问题，规模n的问题拆解为当前选dfs(n-2)+x和不选dfs(n-1)的问题
     */
    /*private int[] nums, memo;

    public int rob(int[] nums) {
        this.nums = nums;
        int n = nums.length;
        memo = new int[n];
        Arrays.fill(memo, -1);
        return dfs(n - 1);
    }

    private int dfs(int i) {
        if (i < 0) return 0;
        if (memo[i] != -1) return memo[i];
        int res = Math.max(dfs(i - 1), dfs(i - 2) + nums[i]);
        memo[i] = res;
        return res;
    }
    */

    /**
     * 上面的过程还是属于递归，下面将其优化为只有归的过程，发现
     * f[i + 2] = Math.max(f[i + 1], f[i] + nums[i]);
     */
    /*public int rob(int[] nums) {
        int n = nums.length;
        int[] f = new int[n + 2];
        for (int i = 0; i < n; i++) {
            f[i + 2] = Math.max(f[i + 1], f[i] + nums[i]);
        }
        return f[n + 1];
    }
    */

    /**
     * 空间优化
     */
    public int rob(int[] nums) {
        int f0 = 0;
        int f1 = 0;
        for (int x : nums) {
            int newF = Math.max(f1, f0 + x);
            f0 = f1;
            f1 = newF;
        }
        return f1;
    }
}
